class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def getKnum(nums1, nums2, s1, s2, k):
            #k最小为1
            #两个数组有一个为空
            if s1 >= len(nums1):
                return nums2[s2 + k - 1]

            if s2 >= len(nums2):
                return nums1[s1 + k - 1]

            if k == 1:
                return min(nums1[s1], nums2[s2])

            #都不为空
            i = min(s1 + k / 2 - 1, len(nums1) - 1)
            j = min(s2 + k / 2 - 1, len(nums2) - 1)
            a = nums1[i]
            b = nums2[j]
            if a < b:
                k = k - (i - s1 + 1)
                s1 = i + 1
            else:
                k = k - (j - s2 + 1)
                s2 = j + 1
            return getKnum(nums1, nums2, s1, s2, k)

        m = len(nums1)
        n = len(nums2)
        left = (m + n + 1) / 2
        right = (m + n + 2) / 2
        return (getKnum(nums1, nums2, 0, 0, left) + getKnum(nums1, nums2, 0, 0, right)) / 2.0
